/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package kuhnmunkresproject;

import java.util.LinkedList;

/**
 *
 * @author Agustin
 */
public class HungarianAlgorithm
{
    /// <summary>
    /// Finds the optimal assignments for a given matrix of agents and costed tasks such that the total cost is
    /// minimized.
    /// </summary>
    /// <param name="costs">A cost matrix; the element at row <em>i</em> and column <em>j</em> represents the cost of
    /// agent <em>i</em> performing task <em>j</em>.</param>
    /// <returns>A matrix of assignments; the value of element <em>i</em> is the column of the task assigned to agent
    /// <em>i</em>.</returns>
    /// <exception cref="ArgumentNullException"><paramref name="costs"/> is <see langword="null"/>.</exception>
    public int[] FindAssignments(int[][] costs)
    {
        //if (costs == null)
        //    throw new ArgumentNullException("costs");

        int h = costs.length;
        int w = costs.length;

        for (int i = 0; i < h; i++)
        {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < w; j++)
                min = Math.min(min, costs[i][j]);
            for (int j = 0; j < w; j++)
                costs[i][j] -= min;
        }

        int[][] masks = new int[h][w];
        boolean[] rowsCovered = new boolean[h];
        boolean[] colsCovered = new boolean[w];
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (costs[i][j] == 0 && !rowsCovered[i] && !colsCovered[j])
                {
                    masks[i][j] = 1;
                    rowsCovered[i] = true;
                    colsCovered[j] = true;
                }
            }
        }
        ClearCovers(rowsCovered, colsCovered, w, h);

        Location[] path = new Location[w * h];
        Location pathStart = new Location();
        int step = 1;
        while (step != -1)
        {
            switch (step)
            {
                case 1:
                    step = RunStep1(costs, masks, rowsCovered, colsCovered, w, h);
                    break;
                case 2:
                    LinkedList<Location> list = new LinkedList<Location>();
                    
                    step = RunStep2(costs, masks, rowsCovered, colsCovered, w, h, list);
                    
                    if(list.size() > 0)
                        pathStart = list.getFirst();
                            
                    break;
                case 3:
                    step = RunStep3(costs, masks, rowsCovered, colsCovered, w, h, path, pathStart);
                    break;
                case 4:
                    step = RunStep4(costs, masks, rowsCovered, colsCovered, w, h);
                    break;
            }
        }

        int[] agentsTasks = new int[h];
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (masks[i][j] == 1)
                {
                    agentsTasks[i] = j;
                    break;
                }
            }
        }
        return agentsTasks;
    }

    private int RunStep1(int[][] costs, int[][] masks, boolean[] rowsCovered, 
            boolean[] colsCovered, int w, int h)
    {
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (masks[i][j] == 1)
                    colsCovered[j] = true;
            }
        }
        int colsCoveredCount = 0;
        for (int j = 0; j < w; j++)
        {
            if (colsCovered[j])
                colsCoveredCount++;
        }
        if (colsCoveredCount == h)
            return -1;
        else
            return 2;
    }

    private int RunStep2(int[][] costs, int[][] masks, boolean[] rowsCovered, boolean[] colsCovered, 
            int w, int h, LinkedList<Location> list)
    {
        Location loc = new Location();
        
        while (true)
        {
            loc = FindZero(costs, masks, rowsCovered, colsCovered, w, h);
            if (loc.Row == -1)
            {
                return 4;
            }
            else
            {
                masks[loc.Row][loc.Column] = 2;
                int starCol = FindStarInRow(masks, w, loc.Row);
                if (starCol != -1)
                {
                    rowsCovered[loc.Row] = true;
                    colsCovered[starCol] = false;
                }
                else
                {
                    //pathStart = (Location)loc.clone();
                    //pathStart.Column = loc.Column;
                    //pathStart.Row = loc.Row;
                    list.add(loc);
                    return 3;
                }
            }
        }
    }

    private int RunStep3(int[][] costs, int[][] masks, boolean[] rowsCovered, 
            boolean[] colsCovered, int w, int h, Location[] path, Location pathStart)
    {
        int pathIndex = 0;
        path[0] = pathStart;
        while (true)
        {
            int row = FindStarInColumn(masks, h, path[pathIndex].Column);
            if (row == -1)
                break;
            pathIndex++;
            path[pathIndex] = new Location(row, path[pathIndex - 1].Column);
            int col = FindPrimeInRow(masks, w, path[pathIndex].Row);
            pathIndex++;
            path[pathIndex] = new Location(path[pathIndex - 1].Row, col);
        }
        ConvertPath(masks, path, pathIndex + 1);
        ClearCovers(rowsCovered, colsCovered, w, h);
        ClearPrimes(masks, w, h);
        return 1;
    }

    private int RunStep4(int[][] costs, int[][] masks, boolean[] rowsCovered, 
            boolean[] colsCovered, int w, int h)
    {
        int minValue = FindMinimum(costs, rowsCovered, colsCovered, w, h);
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (rowsCovered[i])
                    costs[i][j] += minValue;
                if (!colsCovered[j])
                    costs[i][j] -= minValue;
            }
        }
        return 2;
    }

    private void ConvertPath(int[][] masks, Location[] path, int pathLength)
    {
        for (int i = 0; i < pathLength; i++)
        {
            if (masks[path[i].Row][path[i].Column] == 1)
                masks[path[i].Row][path[i].Column] = 0;
            else if (masks[path[i].Row][path[i].Column] == 2)
                masks[path[i].Row][path[i].Column] = 1;
        }
    }

    private Location FindZero(int[][] costs, int[][] masks, boolean[] rowsCovered, 
            boolean[] colsCovered,
        int w, int h)
    {
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (costs[i][j] == 0 && !rowsCovered[i] && !colsCovered[j])
                    return new Location(i, j);
            }
        }
        return new Location(-1, -1);
    }

    private int FindMinimum(int[][] costs, boolean[] rowsCovered, boolean[] colsCovered, 
            int w, int h)
    {
        int minValue = Integer.MAX_VALUE;
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (!rowsCovered[i] && !colsCovered[j])
                    minValue = Math.min(minValue, costs[i][j]);
            }
        }
        return minValue;
    }

    private int FindStarInRow(int[][] masks, int w, int row)
    {
        for (int j = 0; j < w; j++)
        {
            if (masks[row][j] == 1)
                return j;
        }
        return -1;
    }

    private int FindStarInColumn(int[][] masks, int h, int col)
    {
        for (int i = 0; i < h; i++)
        {
            if (masks[i][col] == 1)
                return i;
        }
        return -1;
    }

    private int FindPrimeInRow(int[][] masks, int w, int row)
    {
        for (int j = 0; j < w; j++)
        {
            if (masks[row][j] == 2)
                return j;
        }
        return -1;
    }

    private void ClearCovers(boolean[] rowsCovered, boolean[] colsCovered, int w, int h)
    {
        for (int i = 0; i < h; i++)
            rowsCovered[i] = false;
        for (int j = 0; j < w; j++)
            colsCovered[j] = false;
    }

    private void ClearPrimes(int[][] masks, int w, int h)
    {
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (masks[i][j] == 2)
                    masks[i][j] = 0;
            }
        }
    }

    private class Location implements Cloneable
    {
        public int Row;
        public int Column;

        public Location(){
        }
        
        public Location(int row, int col)
        {
            this.Row = row;
            this.Column = col;
        }
        
        public Object clone() { 
            Object clone = null; 
            try { clone = super.clone(); } 
            catch(CloneNotSupportedException e) { 
            // No deberia suceder 
            } return clone; 
        } 
    }
}
